{"cells":[{"cell_type":"markdown","metadata":{},"source":["# 2025 sujet 01 — Correction de l'exercice 2\n","\n","Correction question par question."]},{"cell_type":"markdown","metadata":{},"source":["## Question 1\n","\n","La méthode `passer_transit` met simplement l'attribut `etat` à la valeur `'transit'`."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["class Colis:\n","    def __init__(self, id, poids, adresse):\n","        self.id = id\n","        self.poids = poids\n","        self.adresse = adresse\n","        self.etat = \"préparé\"\n","\n","    def passer_transit(self):\n","        self.etat = \"transit\""]},{"cell_type":"markdown","metadata":{},"source":["## Question 2\n","\n","On modifie la fonction `ajouter_colis` pour refuser les colis de plus de 25 kg."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def ajouter_colis(liste, colis):\n","    if colis.poids <= 25:\n","        liste.append(colis)\n","    else:\n","        print(\"Dépassement du poids maximal autorisé\")"]},{"cell_type":"markdown","metadata":{},"source":["## Question 3\n","\n","Le nombre de colis est la longueur de la liste."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def nb_colis(liste):\n","    return len(liste)"]},{"cell_type":"markdown","metadata":{},"source":["## Question 4\n","\n","On additionne les poids des colis de la liste."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def poids_total(liste):\n","    total = 0\n","    for c in liste:\n","        total = total + c.poids\n","    return total"]},{"cell_type":"markdown","metadata":{},"source":["## Question 5\n","\n","On construit une nouvelle liste contenant seulement les colis dont l'état est égal au statut demandé."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def liste_colis_etat(liste, statut):\n","    resultat = []\n","    for colis in liste:\n","        if colis.etat == statut:\n","            resultat.append(colis)\n","    return resultat"]},{"cell_type":"markdown","metadata":{},"source":["## Question 6\n","\n","La fonction `tri_decroissant` utilise un **tri par sélection**.\n","\n","À chaque étape, on cherche le colis de poids maximal dans la partie non triée de la liste, puis on l'échange avec l'élément courant.\n","\n","Dans le pire des cas, le coût en comparaisons est : $O(n^2)$."]},{"cell_type":"markdown","metadata":{},"source":["## Question 7\n","\n","On aurait pu utiliser le **tri fusion**.\n","\n","Son coût dans le pire des cas est en : $O(nlog_2(n))$\n"]},{"cell_type":"markdown","metadata":{},"source":["## Question 8\n","\n","On complète la fonction récursive.\n","\n","Cas d'arrêt : si `rang == len(liste)`, il n'y a plus de colis à étudier.\n","\n","Si le colis courant rentre dans la capacité restante, on le prend et on continue avec une capacité diminuée.\n","\n","Sinon, on passe au colis suivant."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def chargement_glouton(liste, rang, capacite):\n","    if rang == len(liste):\n","        return []\n","    elif liste[rang].poids <= capacite:\n","        return [liste[rang]] + chargement_glouton(liste, rang + 1, capacite - liste[rang].poids)\n","    else:\n","        return chargement_glouton(liste, rang + 1, capacite)"]},{"cell_type":"markdown","metadata":{},"source":["## Question 9\n","\n","L'erreur `RecursionError: maximum recursion depth exceeded` peut se produire si le nombre d'appels récursifs devient trop grand.\n","\n","Ici, cela peut arriver avec une très longue liste de colis, car la fonction fait un nouvel appel récursif pour chaque rang. Python limite la profondeur maximale de récursion."]},{"cell_type":"markdown","metadata":{},"source":["## Question 10\n","\n","Version itérative de l'algorithme glouton."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def chargement_glouton2(liste, capacite):\n","    colis_a_charger = []\n","    charge = 0\n","    for colis in liste:\n","        if charge + colis.poids <= capacite:\n","            colis_a_charger.append(colis)\n","            charge = charge + colis.poids\n","    return colis_a_charger"]},{"cell_type":"markdown","metadata":{},"source":["## Script complet de l'exercice 2"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["class Colis:\n","    def __init__(self, id, poids, adresse):\n","        self.id = id\n","        self.poids = poids\n","        self.adresse = adresse\n","        self.etat = \"préparé\"\n","\n","    def passer_transit(self):\n","        self.etat = \"transit\"\n","\n","def ajouter_colis(liste, colis):\n","    if colis.poids <= 25:\n","        liste.append(colis)\n","    else:\n","        print(\"Dépassement du poids maximal autorisé\")\n","\n","def nb_colis(liste):\n","    return len(liste)\n","\n","def poids_total(liste):\n","    total = 0\n","    for c in liste:\n","        total = total + c.poids\n","    return total\n","\n","def liste_colis_etat(liste, statut):\n","    resultat = []\n","    for colis in liste:\n","        if colis.etat == statut:\n","            resultat.append(colis)\n","    return resultat\n","\n","def tri_decroissant(liste):\n","    n = len(liste)\n","    for i in range(n - 1):\n","        min_pos = i\n","        for j in range(i + 1, n):\n","            if liste[j].poids > liste[min_pos].poids:\n","                min_pos = j\n","        temp = liste[i]\n","        liste[i] = liste[min_pos]\n","        liste[min_pos] = temp\n","    return liste\n","\n","def chargement_glouton(liste, rang, capacite):\n","    if rang == len(liste):\n","        return []\n","    elif liste[rang].poids <= capacite:\n","        return [liste[rang]] + chargement_glouton(liste, rang + 1, capacite - liste[rang].poids)\n","    else:\n","        return chargement_glouton(liste, rang + 1, capacite)\n","\n","def chargement_glouton2(liste, capacite):\n","    colis_a_charger = []\n","    charge = 0\n","    for colis in liste:\n","        if charge + colis.poids <= capacite:\n","            colis_a_charger.append(colis)\n","            charge = charge + colis.poids\n","    return colis_a_charger\n","\n","colisA = Colis(\"AC12\", 5.0, \"20 rue de la paix 57000 Metz\")\n","colisB = Colis(\"AF34\", 10.25, \"32 rue du centre 57000 Metz\")\n","liste_colis = []\n","ajouter_colis(liste_colis, colisA)\n","ajouter_colis(liste_colis, colisB)\n","print(nb_colis(liste_colis))\n","print(poids_total(liste_colis))"]}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.x"}},"nbformat":4,"nbformat_minor":5}